package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;

public class Code23_PathWithMaximumProbability {
	public static class Edge {
		public int weight;
		public Node from;
		public Node to;

		public Edge(int weight, Node from, Node to) {
			this.weight = weight;
			this.from = from;
			this.to = to;
		}
	}

	public static class Node {
		public int value;
		public int in;
		public int out;
		public ArrayList<Node> nexts;
		public ArrayList<Edge> edges;

		public Node(int value) {
			this.value = value;
			in = 0;
			out = 0;
			nexts = new ArrayList<>();
			edges = new ArrayList<>();
		}
	}

	public static class Graph {
		public HashMap<Integer, Node> nodes;
		public HashSet<Edge> edges;

		public Graph() {
			nodes = new HashMap<>();
			edges = new HashSet<>();
		}
	}

	public static Graph createGraph(int[][] matrix) {
		Graph graph = new Graph();
		for (int i = 0; i < matrix.length; i++) {
			Integer from = matrix[i][0];
			Integer to = matrix[i][1];
			Integer weight = matrix[i][2];

			if (!graph.nodes.containsKey(from)) {
				graph.nodes.put(from, new Node(from));
			}

			if (!graph.nodes.containsKey(to)) {
				graph.nodes.put(to, new Node(to));
			}

			Node fromNode = graph.nodes.get(from);
			Node toNode = graph.nodes.get(to);

			Edge newEdge = new Edge(weight, fromNode, toNode);
			fromNode.nexts.add(toNode);
			fromNode.out++;
			toNode.in++;

			fromNode.edges.add(newEdge);
			graph.edges.add(newEdge);
		}
		return graph;
	}

	public static class DistanceNode {
		public Node node;
		public double dis;

		public DistanceNode(Node v, double dis) {
			this.node = v;
			this.dis = dis;
		}

		@Override
		public String toString() {
			return "DistanceNode [node=" + node + ", dis=" + dis + "]";
		}
	}

	public static class DistanceNodeComparator implements Comparator<DistanceNode> {
		@Override
		public int compare(DistanceNode o1, DistanceNode o2) {
			if (o1.dis > o2.dis) {
				return -1;

			} else if (o1.dis < o2.dis) {
				return 1;
			}

			return 0;
		}
	}

	public static HashMap<Node, Double> dijkstra1(Node head, Map<Integer, Double> succProbMap) {
		HashMap<Node, Double> distanceMap = new HashMap<>();
		if (head == null) {
			distanceMap.put(head, 0.0);
			return distanceMap;
		}

		distanceMap.put(head, 1.0);
		HashSet<Node> selectedNodes = new HashSet<>();
		selectedNodes.add(null);

		PriorityQueue<DistanceNode> queue = new PriorityQueue<>(new DistanceNodeComparator());
		DistanceNode headDistanceMap = new DistanceNode(head, 1.0);
		queue.offer(headDistanceMap);

		while (!queue.isEmpty()) {
			DistanceNode disNode = queue.poll();
			Node minNode = disNode.node;
			double distance = disNode.dis;

			if (!selectedNodes.contains(minNode)) {
				for (Edge edge : minNode.edges) {
					Node toNode = edge.to;
					if (selectedNodes.contains(toNode))
						continue;

					if (!distanceMap.containsKey(toNode)) {
						distanceMap.put(toNode, distance * succProbMap.get(edge.weight));

					} else {
						distanceMap.put(toNode,
								Math.max(distanceMap.get(toNode), distance * succProbMap.get(edge.weight)));
					}

					selectedNodes.add(minNode);
					DistanceNode toDistanceMap = new DistanceNode(toNode, distanceMap.get(toNode));
					queue.offer(toDistanceMap);
				}
			}
		}

		return distanceMap;
	}

	public static double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {

		int[][] matrix = new int[edges.length * 2][3];
		Map<Integer, Double> succProbMap = new HashMap<>();

		int j = 0;
		for (int i = 0; i < edges.length; i++) {
			int from = edges[i][0];
			int to = edges[i][1];
			succProbMap.put(i, succProb[i]);
			int weight = i;

			int[] temp = new int[3];
			temp[0] = from;
			temp[1] = to;
			temp[2] = weight;

			matrix[j++] = temp;
		}

		for (int i = 0; i < edges.length; i++) {
			int from = edges[i][1];
			int to = edges[i][0];
			succProbMap.put(i, succProb[i]);
			int weight = i;

			int[] temp = new int[3];
			temp[0] = from;
			temp[1] = to;
			temp[2] = weight;

			matrix[j++] = temp;
		}

		Graph graph = createGraph(matrix);

		Node startNode = graph.nodes.get(start);
		if (startNode == null) {
			return 0.000;
		}

		HashMap<Node, Double> dMap = dijkstra1(startNode, succProbMap);
		Node endNode = graph.nodes.get(end);

		return dMap.get(endNode) != null ? dMap.get(endNode) : 0.000;
	}

//	5
//	[[1,4],[2,4],[0,4],[0,3],[0,2],[2,3]]
//	[0.37,0.17,0.93,0.23,0.39,0.04]
//	3
//	4

//	0.21390
	public static void main(String[] args) {
//		{
//			int n = 3;
//			int[][] edges = new int[][] { { 0, 1 }, { 1, 2 }, { 0, 2 } };
//			double[] succProb = new double[] { 0.5, 0.5, 0.2 };
//			int start = 0;
//			int end = 2;
//
//			System.out.println(maxProbability(n, edges, succProb, start, end));
//		}

		{
			int n = 5;
			int[][] edges = new int[][] { { 1, 4 }, { 2, 4 }, { 0, 4 }, { 0, 3 }, { 0, 2 }, { 2, 3 } };
			double[] succProb = new double[] { 0.37, 0.17, 0.93, 0.23, 0.39, 0.04 };
			int start = 3;
			int end = 4;

			System.out.println(maxProbability(n, edges, succProb, start, end));
		}

//		500
//		[[193,229],[133,212],[224,465]]
//		[0.91,0.78,0.64]
//		4
//		364

//		0.00000
		{
			int n = 500;
			int[][] edges = new int[][] { { 193, 229 }, { 133, 212 }, { 224, 465 } };
			double[] succProb = new double[] { 0.91, 0.78, 0.64 };
			int start = 4;
			int end = 364;

			System.out.println(maxProbability(n, edges, succProb, start, end));
		}
	}
}
